package com.tyrone.leetcode.editor.cn;

/**
 * 完全背包问题
 *
 * @author yelong.xie
 * @date 2024/1/29 23:51
 */
public class PackageProblemComplete {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxValue(2, 5, new int[]{1, 2}, new int[]{1, 2}));
    }

    /**
     * 有N件物品和一个容量是 V的背包。每件物品有且只有一件。
     * 第 i 件物品的体积是 v[i] ，价值是 w[i]。
     * 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
     * 输入: N = 2, C = 5, v = [1,2], w = [1,2]
     * 输出: 5
     * 解释: 选一件物品 1，再选两件物品 2，可使价值最大。
     */
    static class Solution {
        /**
         * int[N][C] 复杂度
         * @param N
         * @param C
         * @param v
         * @param w
         * @return
         */
//        public int maxValue(int N, int C, int[] v, int[] w) {
//            // dp[i][j]代表考虑前 i件物品，放入一个容量为j的背包可以获得的最大价值。
//            int[][] dp = new int[N][C + 1];
//            //选择第一件的情况下
//            for (int i = 0; i <= C; i++) {
//                int maxK = i / v[0]; //当前容量下能容纳多少件
//                dp[0][i] = maxK*w[0];
//            }
//
//            for (int i = 1; i < N; i++) {
//                for (int j = 0; j <= C; j++) {
//                    //不选择i这件商品
//                    int noSelect = dp[i-1][j];
//
//                    //选择这件商品
//                    int select = 0;
//
//                    for (int k = 1; ; k++) {
//                        //超过k件
//                        if (v[i]*k > j){
//                            break;
//                        }
//                        select = Math.max(dp[i-1][j-v[i]*k]+w[i]*k,select);
//                    }
//                    dp[i][j] = Math.max(select,noSelect);
//                }
//            }
//            return dp[N-1][C];
//        }

        /**
         * int[2][C] 复杂度
         * @param N
         * @param C
         * @param v
         * @param w
         * @return
         */
//        public int maxValue(int N, int C, int[] v, int[] w) {
//            // dp[i][j]代表考虑前 i件物品，放入一个容量为j的背包可以获得的最大价值。
//            int[][] dp = new int[2][C + 1];
//            //选择第一件的情况下
//            for (int i = 0; i <= C; i++) {
//                int maxK = i / v[0]; //当前容量下能容纳多少件
//                dp[0][i] = maxK*w[0];
//            }
//
//            for (int i = 1; i < N; i++) {
//                for (int j = 0; j <= C; j++) {
//                    //不选择i这件商品
//                    int noSelect = dp[(i-1)&1][j];
//
//                    //选择这件商品
//                    int select = 0;
//
//                    for (int k = 1; ; k++) {
//                        //超过k件
//                        if (v[i]*k > j){
//                            break;
//                        }
//                        select = Math.max(dp[(i-1)&1][j-v[i]*k]+w[i]*k,select);
//                    }
//                    dp[i][j] = Math.max(select,noSelect);
//                }
//            }
//            return dp[N-1][C];
//        }

        /**
         * [C] 空间复杂度
         *
         * @param N
         * @param C
         * @param v
         * @param w
         * @return
         */
        public int maxValue(int N, int C, int[] v, int[] w) {
            // dp[j]放入一个容量为j的背包可以获得的最大价值。
            int[] dp = new int[C + 1];

            for (int i = 0; i < N; i++) {
                for (int j = 0; j <= C; j++) {
                    //不考虑第i件物品的情况(选择0件物品i)
                    int n = dp[j];
                    //考虑第i件物品的情况
                    int y = j - v[i] >= 0 ? dp[j - v[i]] + w[i] : 0;
                    dp[j] = Math.max(n,y);
                }
            }
            return dp[C];
        }

    }
}
